package cn.njupt.cmpSort;

import java.util.LinkedList;
import java.util.List;

//希尔排序
public class ShellSort<E extends Comparable<E>> extends Sort<E> {
    private List<Integer> steps;
    @Override
    public void sort() {
        computeSteps();
        for (int step:steps){
            //按照步长进行分割，然后对矩阵进行按列排序
            sort(step);
        }
    }

    private void sort(int step) {
        for(int col=0;col<step;col++){
            //下面是个插入排序的过程
            for(int begin=col+step;begin<array.length;begin+=step){
                int curIndex=begin;
                E initalValue=array[begin];
                while(curIndex-col>0&&cmpElements(array[curIndex-step],initalValue)>0){
                    array[curIndex]=array[curIndex-step];
                    curIndex-=step;
                }
                array[curIndex]=initalValue;
            }
        }
    }
    //计算步长
    public void computeSteps(){
        steps=new LinkedList<>();
        int step=array.length;
        while((step>>=1)>0){
            steps.add(step);
        }
    }
}
